/***************************************************************************
 *   Copyright (C) 2009 by Eduardo Gurgel Pinho                            *
 *   edgurgel@gmail.com                                                    *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 3 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
***************************************************************************/

#include "jarvis.h"

#include "vector.h"

#include <algorithm>
#include <cmath>
#include <limits>
#ifdef DEBUG
#include <iostream>
#endif

#include <boost/foreach.hpp>
#include <boost/weak_ptr.hpp>

#define foreach BOOST_FOREACH

namespace Tujchi {

bool vector_compare(const Vector& _vector1, const Vector& _vector2) {
	if(_vector1.y < _vector2.y)
		return true;
	else if(_vector1.y == _vector2.y)
		return true;
	else
		return false;
}

Jarvis::Jarvis(std::vector<Vector> _points) : points(_points) { 
	std::sort(points.begin(), points.end());
}

Jarvis::~Jarvis(void) { }

std::vector<Vector> Jarvis::convex_hull(void) {
	std::vector<Vector> result;


	result.push_back(points[0]);
#ifdef DEBUG
	std::cout << "Ponto adicionado: "  << std::endl;
	points[0].show();
#endif
	
	Vector test_vector = Vector(result[0].x+ 100,result[0].y+0.1) - result[0];
	Vector convex_hull_point;
	Vector last_convex_hull_point = result[0];
	std::vector<Vector>::iterator chosen;
	bool gambi = true;
	while(1) {
		double min_angle = std::numeric_limits<double>::infinity();
#ifdef DEBUG
		std::cout << "Vetor de teste" << std::endl;
		test_vector.show();
#endif
		bool choose = false;
		for(std::vector<Vector>::iterator i = points.begin(); i != points.end(); i++ ) {
			if(last_convex_hull_point == result[0] && *i == result[0]) continue;
			Vector point = *i;
			Vector test = point - last_convex_hull_point;
			double angle = (test_vector.normalize()).angle(test.normalize());
#ifdef DEBUG
			std::cout << "Ponto: "<< std::endl;
			point.show();
			std::cout << "Angulo : " << angle/M_PI*180.0 << std::endl;
#endif
			if(angle < 0.0) angle = (2.0*M_PI) + angle;
#ifdef DEBUG
			std::cout << "Angulo : " << angle/M_PI*180.0 << std::endl;
			std::cout << "Angulo minimo : " << min_angle/M_PI*180.0 << std::endl;
#endif
			if(angle < min_angle) {
				min_angle = angle;
				convex_hull_point = point;
				chosen = i;
				choose = true;
			} else if(angle == min_angle) {
				if(convex_hull_point.length() < point.length()) {
					min_angle = angle;
					convex_hull_point = point;
					chosen = i;
					choose = true;
				}
			}
		}
		if(convex_hull_point == (result[0]) && !gambi) break;
		else {
#ifdef DEBUG
			std::cout << "Resultado do tamanho: " << result.size() << std::endl;
#endif
			result.push_back(Vector(convex_hull_point));
			if(choose) points.erase(chosen);
			test_vector = convex_hull_point - last_convex_hull_point;
			last_convex_hull_point = convex_hull_point;
#ifdef DEBUG
			std::cout << "Ponto escolhido: " << std::endl;
			convex_hull_point.show();
#endif
		}
		gambi = false;
#ifdef DEBUG
		std::cout << "----------" << std::endl;
#endif
	}

	return result;
}

void Jarvis::insert_point(Vector _point) {
	points.push_back(_point);
}

}

